mod tree_node;

use tree_node::TreeNode;
use std::rc::Rc;
use std::cell::RefCell;

struct Solution;

impl Solution {
    pub fn construct_from_pre_post(pre: Vec<i32>, post: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        // 需要考虑的问题
        // 子树如果为空
        //  1 2 4 5
        // 4 5 2 1

        // 前序数组第二个节点就是左子树的root节点
        // 从后续数组中遍历到它,从第一个节点到它就是左子树的节点结合

        // 后续节点的最后第二个节点就是右子树的root节点
        // 从前序数组中遍历得到它，从它开始到最后的节点就是右子树的节点集合

        let len = pre.len();

        match len {
            0 => None,
            _ => {
                Solution::help(&pre, 0, len, &post, 0, len)
            }
        }
    }

    // 辅助函数
    fn help(pre: &[i32], pre_start: usize, pre_end: usize, post: &[i32], post_start: usize, post_end: usize) -> Option<Rc<RefCell<TreeNode>>> {
        let root = Rc::new(RefCell::new(TreeNode::new(pre[pre_start])));

        if pre_start + 1 == pre_end {
            return Some(root);
        }

        // if pre_start+2==pre_end{
        //     let left=Some(Rc::new(RefCell::new(TreeNode::new(pre[pre_start+1]))));
        //     root.borrow_mut().left=left;
        //     return Some(root);
        // }

        // 1
        let left_root = pre[pre_start + 1];
        // 1
        let post_left_root_index = Solution::search(post, post_start, post_end, left_root);

        // 1
        let right_root = post[post_end - 2];
        // 1
        let pre_right_root_index = Solution::search(pre, pre_start, pre_end, right_root);

        // println!("{} {}",pre_start+1,pre_right_root_index+1);
        let (left, right) =
            if post_left_root_index == post_end - 2 {
                (
                    Solution::help(pre, pre_start + 1, pre_end, post, post_start, post_end - 1),
                    None
                )
            } else {
                (
                    Solution::help(pre, pre_start + 1, pre_right_root_index, post, post_start, post_left_root_index + 1),
                    Solution::help(pre, pre_right_root_index, pre_end, post, post_left_root_index + 1, post_end - 1)
                )
            };

        root.borrow_mut().left = left;
        root.borrow_mut().right = right;

        Some(root)
    }

    fn search(vec: &[i32], start: usize, end: usize, value: i32) -> usize {
        for (i, item) in vec.iter().enumerate().skip(start).take(end - start) {
            if *item == value {
                return i;
            }
        }
        // 生产环境要做错误处理
        0
    }
}

fn main() {
    Solution::construct_from_pre_post(vec![], vec![]);
}
